On-chip caches are used in various microprocessor designs to improve performance by storing frequently used information in fast, on-chip memories. Performance is improved because information can be retrieved quickly during program execution. Various types of cache architectures exist. Direct mapped caches, for example, always map a location in main memory to the same location in the cache memory. Whether or not the desired data is in the cache (a “hit”) or not (a “miss”) is determined by looking at a particular location in the cache memory, given a particular main memory address. By contrast, fully associative caches allow a location in main memory to be mapped to any location within the cache memory. In order to determine whether or not a cache hit or miss has occurred, a fully associated cache memory must be searched. If the entire cache is in use, it may be necessary to search the entire cache. Direct mapped caches have higher search speeds than fully associative caches. Fully associative caches have higher hit/miss ratios than direct mapped caches.
An alternative cache architecture that strikes a balance between a direct mapped and a fully associative cache is an N-Way set associative cache. In such a cache design a particular memory location maps to a group or “set” of cache locations, any one of which may be used to cache the data for a particular location in main memory. To determine if a hit or miss has occurred, only those locations within the set corresponding to the mapped main memory address need be searched. By varying the value of “N” (the number of sets) a desired balance can be achieved between the speed of the search and the hit/miss ratio.
To improve search speeds in an N-Way set associative cache, the main memory addresses of the cached data stored within a set may simultaneously be accessed and compared with the desired address, thus avoiding having to search the set. This can be accomplished by subdividing the cache memory into sub-arrays, each sub-array comprising one element of any given set. The N memory sub-arrays within the cache (representing the N “Ways” of the cache) are accessed simultaneously with each memory access. Thus, even though data from only one Way may be used, all N Ways must be accessed in order to read data that is stored in the cache (a hit). Accessing all N-Ways in this manner can result in significant power consumption, which can be problematic for a battery-operated device.